home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / info-service / wais / ir-book-sources / thesauri / hierarky.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-08  |  29.4 KB  |  823 lines
  1. /*
  2.  
  3.    PROGRAM NAME: hierarky.c
  4.  
  5.    PURPOSE:  This program will generate a hierarchy in two ways.
  6.  
  7.              1)  It can simply read the parent-child links from an input file
  8.                  and store the links in the inverted file structure,
  9.        OR
  10.              2)  It can use the Rada algorithm which splits up words
  11.                  into different frequency groups and then builds links between
  12.                  them.
  13.  
  14.    INPUT FILES REQUIRED:  (Depends on the option selected).
  15.    
  16.          Option 1:  requires inverted file and link file.
  17.          Option 2:  requires inverted file.
  18.  
  19.              1)  inverted file: sequences of
  20.         
  21.                  term      document number     weight.
  22.  
  23.                  (multiple entries for any term should be grouped together)
  24.  
  25.              2)  links file: sequences of
  26.  
  27.                  parent term     child term
  28.  
  29.    NOTES:    Filters such as stop lists and stemmers should be used
  30.              before running this program.
  31.  
  32.    PARAMETERS TO BE SET BY USER: 
  33.    
  34.              1)  MAXWORD:  identifies the maximum size of a term
  35.              2)  NUMBER_OF_LEVELS:  specifies the desired number of levels 
  36.                  in the thesaurus hierarchy to be generated, used by the 
  37.                  Rada algorithm
  38.  
  39.    COMMAND LINE:  (INPUT & OUTPUT FILES ARE SPECIFIED INTERACTIVELY)
  40.  
  41.              hierarky    
  42.  
  43.  
  44. ****************************************************************************/
  45.  
  46. #include <stdio.h>
  47. #include <string.h>
  48. #include <math.h>
  49. #define MAXWORD 20             /* maximum size of a term                 */
  50. #define NUMBER_OF_LEVELS 10     /* # of levels desired in the thesaurus   */
  51.  
  52. struct doclist {               /* sequences of document # and weight pairs*/
  53.   int doc;                     /* document number                        */
  54.   float weight;                /* term weight in document                */
  55.   struct doclist *nextdoc;     /* ptr. to next doclist record            */
  56. } doclistfile;
  57.  
  58. struct parentlist {
  59.   char term[MAXWORD];          /* parent term                            */
  60.   struct invert *parent;       /* ptr. to parent term in inverted file   */
  61.   struct parentlist *nextparent; /* ptr. to next parentlist record       */
  62. } parentfile;
  63.  
  64. struct childlist {
  65.   char term[MAXWORD];          /* child term                             */
  66.   struct invert *child;        /* ptr. to child term in inverted file    */
  67.   struct childlist *nextchild; /* ptr. to next childlist record          */
  68. } childfile;
  69.  
  70. struct invert {                /* inverted file                          */
  71.   char term[MAXWORD];          /* term                                   */
  72.   struct doclist *doc;         /* sequences of document # and weight     */
  73.   struct parentlist *parents;  /* ptr. to parent terms                   */
  74.   struct childlist *children;  /* ptr. to child terms                    */
  75.   int level;                   /* thesaurus level based on term frequency*/
  76.   struct invert *nextterm;     /* ptr. to next invert record             */
  77. } invfile;
  78.  
  79. struct invert *startinv;       /* ptr. to first record in inverted file  */
  80. struct invert *lastinv;        /* ptr. to last record in inverted file   */
  81. struct doclist *lastdoc;       /* ptr. to last document in doclist       */
  82.  
  83.  
  84. static char currentterm[MAXWORD]; /* tracks current term in inverted file   */
  85. static int Number_of_docs;      /* total # of documents which is computed */
  86.  
  87. static struct invert *get_mem_invert();        /* these 4 functions will obtain        */
  88. static struct doclist *get_mem_doclist();      /* memory for records.  The type of     */
  89. static struct parentlist *get_mem_parentlist();/* is indicated by the name of          */
  90. static struct childlist *get_mem_childlist();  /* the function                         */
  91.  
  92. static FILE *input;                 /* inverted file                           */
  93. static FILE *input1;                /* link file                               */
  94. static FILE *output;                /* holds any output                        */
  95.  
  96. static
  97. float cohesion(),                   /* compute cohesion between two terms       */
  98.       total_wdf(),                  /* compute total frequency of term in dbse. */
  99.       get_freq_range();  
  100. static
  101. void  read_invfile(),               /* read in the inverted file                */
  102.       read_links(),                 /* read in the links file                   */
  103.       add_link(),                   /* called within read_links()               */
  104.       pr_invert(),                  /* print the inverted file                  */
  105.       add_invert(),                 /* called within read_invfile()             */
  106.       write_levels(),               /* initialize the levels information        */
  107.       generate_Rada_hierarchy(),    /* generate the Rada hierarchy              */
  108.       get_term_data();              /* get basic information about terms        */
  109.  
  110. struct invert *find_term();         /* searches for term in inverted file and   */
  111.                                     /* returns its address.                     */
  112.  
  113. int main(argc)
  114. int argc;
  115. {
  116.  
  117. char ch, fname[128];
  118.  
  119. startinv = NULL; lastinv = NULL; lastdoc = NULL;
  120. currentterm[0] = '\0'; Number_of_docs = 0;
  121.  
  122. if (argc>1)
  123.   {
  124.   (void) printf("There is an error in the command line\n");
  125.   (void) printf("Correct usage is:\n");
  126.   (void) printf("hierarchy\n");
  127.   exit(1);
  128.   }
  129.  
  130. (void) printf("\nMake a selection\n");
  131. (void) printf("To simply read links from a link file enter 1\n");
  132. (void) printf("To use Rada's algorithm to generate links enter 2\n");
  133. (void) printf("To quit enter 3\n");
  134. (void) printf("Enter selection: ");
  135.  
  136. ch=getchar();
  137.  
  138. switch(ch)
  139.   {
  140.   case '1':
  141.       (void) printf("\nEnter name of inverted file: ");
  142.       (void) scanf("%s",fname);
  143.       if((input=fopen(fname,"r"))==NULL){
  144.         (void) printf("cannot open file %s\n",fname);
  145.         exit(1);
  146.       }
  147.       (void) printf("Enter name of link file: ");
  148.       (void) scanf("%s",fname);
  149.       if((input1=fopen(fname,"r"))==NULL){
  150.         (void) printf("cannot open file %s\n",fname);
  151.         exit(1);
  152.       }
  153.       (void) printf("Enter name of output file: ");
  154.       (void) scanf("%s",fname);
  155.       if((output=fopen(fname,"w"))==NULL){
  156.         (void) printf("cannot open file %s\n",fname);
  157.         exit(1);
  158.       }
  159.       read_invfile();
  160.       (void) fprintf(output,"\nINVERTED FILE\n\n");
  161.       pr_invert();
  162.       read_links(); 
  163.       (void) fprintf(output,"\nINVERTED FILE WITH LINK INFORMATION\n\n");
  164.       pr_invert();
  165.       (void) fclose(input); (void) fclose(input1); (void) fclose(output);
  166.       break;
  167.   case '2':
  168.       (void) printf("\nEnter name of inverted file: ");
  169.       (void) scanf("%s",fname);
  170.       if((input=fopen(fname,"r"))==NULL){
  171.         (void) printf("cannot open file %s\n",fname);
  172.         exit(1);
  173.       }
  174.       (void) printf("Enter name of output file: ");
  175.       (void) scanf("%s",fname);
  176.       if((output=fopen(fname,"w"))==NULL){
  177.         (void) printf("cannot open file %s\n",fname);
  178.         exit(1);
  179.       }
  180.       read_invfile();
  181.       (void) fprintf(output,"\nINVERTED FILE\n\n");
  182.       pr_invert();
  183.       generate_Rada_hierarchy();
  184.       (void) fprintf(output,"\nINVERTED FILE AFTER GENERATING RADA HIERARCHY\n\n");
  185.       pr_invert();
  186.       (void) fclose(input); (void) fclose(output);
  187.       break;
  188.   case '3':
  189.       exit(0);
  190. }
  191.  
  192. return(0);
  193.  
  194. }
  195.  
  196.  
  197. /***************************************************************************
  198.  
  199.      read_invfile()
  200.  
  201.      Returns:  void
  202.  
  203.      Purpose:  Read in the inverted file entries from the disk file
  204.  
  205. **/
  206.  
  207. static void read_invfile()
  208. {
  209. int docid;              /* holds current document number               */
  210. char temp[MAXWORD];     /* holds current term                          */
  211. float weight;           /* holds current term weight                   */
  212. struct doclist *p;      /* structure to store doc#-weight pair         */
  213.  
  214. (void) fscanf(input,"%s%d%f",temp,&docid,&weight);  /* read next line */
  215. while (strlen(temp) > 0)
  216.       /* while its found a legitimate term    */
  217. {
  218. if (!strncmp(currentterm,temp,MAXWORD)) { 
  219.     /* if this term has previously been entered in inverted file then   */
  220.     /* only need to attach a doclist record to the same entry           */
  221.    p = get_mem_doclist();     /* get memory for doclist record           */ 
  222.    p->doc = docid;           /* assign document number     */
  223.    p->weight = weight;       /* assign term weight         */
  224.    p->nextdoc = NULL; 
  225.    if (lastdoc) lastdoc->nextdoc = p;   /* connect p to the doclist chain
  226.                    for this term if it already exists                   */
  227.    lastdoc = p;    /* set this global variable                          */
  228. }
  229. else add_invert(docid,temp,weight);
  230.       /* else term is a brand new term & need to make a new inverted file entry */
  231. temp[0] = '\0';   
  232. (void) fscanf(input,"%s%d%f",temp,&docid,&weight);  /* read next line   */
  233. }
  234. }
  235.  
  236. /***************************************************************************
  237.  
  238.      add_invert(docid,temp,weight)
  239.  
  240.      Returns:  void
  241.  
  242.      Purpose:  Start a new entry in the inverted file.  It is called in the
  243.                read_invfile function when a new term is read from the input
  244.                file.
  245.  
  246. **/
  247.  
  248. static void add_invert(docid,temp,weight)
  249. int docid;                              /* in: document number       */
  250. char temp[MAXWORD];                     /* in: new index term        */
  251. float weight;                           /* in: index term weight     */
  252. {
  253. struct invert *p;                       /* p will get attached to inverted file  */
  254.  
  255. p = get_mem_invert();                    /* get memory for p          */
  256. (void) strncpy(p->term,temp,MAXWORD);   /* copy over the term        */ 
  257. p->parents = NULL;                      /* to begin this term has no parent terms*/
  258. p->children = NULL;                     /* also no child terms       */
  259. p->doc = get_mem_doclist();              /* start a doclist structure */
  260. p->doc->doc = docid;                    /* assign document number    */
  261. p->doc->weight = weight;                /* assign term weight        */
  262. p->doc->nextdoc = NULL;
  263. p->nextterm = NULL;
  264. if (startinv == NULL) startinv = p;
  265.    /* if this is the first entry in inverted file, then update global variable   */
  266. if (lastinv) lastinv->nextterm = p; /* update ptr. to last inverted file record  */
  267. lastinv = p;
  268. lastdoc = p->doc;                      /* update ptr. to last document*/
  269. (void) strncpy(currentterm,temp,MAXWORD); /* update global variable current term */
  270. }                                  /* to the new term just added          */
  271.  
  272. /***************************************************************************
  273.  
  274.      read_links()
  275.  
  276.      Returns:  void
  277.  
  278.      Purpose:  Read parent-child link information from a file and record
  279.      links in the inverted record structure 
  280.  
  281. **/
  282.  
  283. static void read_links()
  284. {
  285. char parent[MAXWORD],     /* tracks parent term        */
  286.      child[MAXWORD];      /* tracks child term         */
  287.  
  288. (void) fscanf(input1,"%s%s",parent,child);  /* read input line    */
  289. while (strlen(parent) > 0)
  290.     /* while a legitimate parent has been found   */
  291. {
  292. add_link(parent,child);  /* this function will add the appropriate links in   */
  293.                          /* the inverted file                                 */
  294. child[0] = '\0'; parent[0] = '\0';  /*  now throw out the old parent & child  */
  295. (void) fscanf(input1,"%s%s",parent,child);   /* read next input line          */
  296. }
  297. }
  298.  
  299. /***************************************************************************
  300.  
  301.      add_link(parent,child)
  302.  
  303.      Returns:  void. 
  304.  
  305.      Purpose:  Used within read_links.  Basically, for each parent-child
  306.                link specified, it adds the appropriate link information into 
  307.                the inverted file.  
  308.  
  309.      Notes:    If a term in the link file is not in the inverted file then
  310.                the program will give a suitable message and exit.
  311.  
  312. **/
  313.  
  314. static void add_link(parent,child)
  315. char parent[MAXWORD],                 /* in: holds the parent term          */
  316.      child[MAXWORD];                  /* in: holds the child term           */
  317. {
  318. struct invert *p,              /* holds add. of parent term in inv. file    */
  319.               *q;              /* holds add. of child term in inv. file     */
  320. struct parentlist *new_parent; /* structure used to store parent info.      */
  321. struct childlist *new_child;   /* structure used to store child info.       */
  322.  
  323. p = find_term(parent);         /* find address of parent term               */
  324. if (!p){ printf("\nPlease check the input files.\n");
  325.          printf("\nParent term %s is not in the inverted file\n",parent);
  326.          exit(0);}
  327. q = find_term(child);          /* find address of child term                */
  328. if (!q){ printf("\nPlease check the input files. Output may be incorrect.\n");
  329.          printf("\nChild term %s is not in the inverted file\n",child);
  330.          exit(0);}
  331.  
  332. /* first add parent links for given child */
  333.  
  334. new_parent = get_mem_parentlist();       /* get memory for parentlist record*/
  335. (void) strncpy(new_parent->term,parent,MAXWORD);    /* copy over parent term*/
  336. new_parent->parent = p;     /* store address of parent term in inverted file*/
  337. if (q->parents == NULL) {     /* i.e. no parents listed for given child yet */ 
  338.    q->parents = new_parent;                       /* first parent link made */
  339.    new_parent->nextparent = NULL;
  340. }
  341. else {                  /* at least 1 parent already listed for given child */ 
  342.    new_parent->nextparent = q->parents;/* attach newparent to front of list */
  343.    q->parents = new_parent;
  344. }
  345.  
  346. /* next add child links for given parent */
  347.  
  348. new_child = get_mem_childlist();         /* get memory for childlist record */
  349. (void) strncpy(new_child->term,child,MAXWORD);     /* copy over child term  */
  350. new_child->child = q;       /* store address of child term in inverted file */
  351. if (p->children == NULL) {       /* no children listed for given parent yet */
  352.    p->children = new_child;                        /* first child link made */
  353.    new_child->nextchild = NULL;
  354. }
  355. else {                  /* at least 1 child already listed for given parent */
  356.    new_child->nextchild = p->children; /* attach newchild to front of list  */
  357.    p->children = new_child;
  358. }
  359. }
  360.  
  361. /***************************************************************************
  362.  
  363.      pr_invert()
  364.  
  365.      Returns:  void
  366.  
  367.      Purpose:  Print the inverted file.  It prints each term, its
  368.      associated document numbers, term-weights and parent child terms.
  369.  
  370. **/
  371.  
  372. static void pr_invert()
  373. {
  374. struct invert *inv_addr;       /* tracks address of current inv. file record  */
  375. struct doclist *doc_addr;      /* tracks address of current doclist record    */
  376. struct parentlist *parent_addr;/* tracks address of current parentlist record */
  377. struct childlist *child_addr;  /* tracks address of current childlist record  */
  378.  
  379. inv_addr = startinv;                          /* begin at top of inverted file*/
  380. while (inv_addr) {                            /* while a legitimate term....  */
  381.   (void) fprintf(output,"TERM: %s\nPARENT TERMS: ",inv_addr->term); 
  382.   parent_addr = inv_addr->parents;             /* find addr. of first parent  */
  383.   while (parent_addr) {                        /* printing all parents        */ 
  384.      (void) fprintf(output,"%s ",parent_addr->term);
  385.      parent_addr = parent_addr->nextparent;    /*loop through remaining parents*/
  386.   }
  387.   (void) fprintf(output,"\nCHILD TERMS: ");
  388.   child_addr = inv_addr->children;             /* find addr. of first child    */
  389.   while (child_addr) {                         /* printing all children        */
  390.      (void) fprintf(output,"%s ",child_addr->term);
  391.      child_addr = child_addr->nextchild;       /*loop through remaining children */
  392.   }
  393.   (void) fprintf(output,"\n\n");
  394.   (void) fprintf(output,"                    DOCUMENT NUMBER                TERM WEIGHT\n");
  395.   doc_addr = inv_addr->doc;                /* find addr. of first associated doc.*/
  396.   while (doc_addr) {                          /* print all docs. and term weights*/
  397.      (void) fprintf(output,"                    %-30d ",doc_addr->doc);
  398.      (void) fprintf(output,"%-10.5f\n",doc_addr->weight);
  399.      doc_addr = doc_addr->nextdoc;            /* loop through remaining documents*/
  400.   }
  401.   (void) fprintf(output,"\n");
  402.   inv_addr = inv_addr->nextterm;               /*  go to next inverted file entry */
  403. }
  404. }
  405.  
  406.  
  407. /***************************************************************************
  408.  
  409.      total_wdf(term)
  410.  
  411.      Returns:  float
  412.  
  413.      Purpose:  Compute total within document frequency for specified term 
  414.                in the database 
  415.  
  416. **/
  417.  
  418. static float total_wdf(term)
  419. char term[MAXWORD];                /* in: term for which total_wdf is required */
  420. {
  421. struct invert *term_addr;          /* add. of above term in inverted file      */
  422. struct doclist *doc_ad;            /* tracks add. of associated doclist record */
  423. float totalwdf;                    /* tracks total wdf                         */
  424.  
  425. totalwdf = 0.0;
  426. term_addr = find_term(term);       /* obtain address of the term in inv. file  */
  427. if (term_addr) {                   /* if term was found                        */
  428.   doc_ad = term_addr->doc;         /* find address of associated doclist record*/
  429.   while (doc_ad) {
  430.     totalwdf = totalwdf + doc_ad->weight;  /* loop through doclist records to  */
  431.     doc_ad = doc_ad->nextdoc;              /* compute the total weight         */
  432.   }
  433. }
  434. else (void) fprintf(output,"Term %s is not in the inverted file.  Could lead to problems\n",term);
  435. return(totalwdf);
  436. }
  437.  
  438. /***************************************************************************
  439.  
  440.    get_freq_range(minimum,maximum)
  441.  
  442.    Returns:  float
  443.  
  444.    Purpose:  Compute the difference between the maximum total term frequency
  445.              and the minimum total term frequency observed in the inverted file. 
  446.  
  447. **/
  448.  
  449. static float get_freq_range(minimum, maximum)
  450. float *minimum,            /* out: returns minimum totalwdf      */
  451.       *maximum;            /* out: returns maximum totalwdf      */
  452. {
  453. struct invert *inv_addr;
  454. float freq, max, min;
  455.  
  456. inv_addr = startinv;    /* begin at top of inverted file         */
  457. /* initialize min and max to equal frequency of 1st term in file */
  458. if (inv_addr) {
  459.   freq = total_wdf(inv_addr->term);
  460.   min = freq; max = freq;
  461.   inv_addr = inv_addr->nextterm; /* go to next term in inv. file */
  462. }
  463. while (inv_addr) {
  464. /* while a legitimate term compare with max and min.             */
  465.   freq = total_wdf(inv_addr->term);
  466.   if (freq > max) max = freq;
  467.   if (freq < min) min = freq;
  468.   inv_addr = inv_addr->nextterm; /* go to next term in inv. file */
  469. }
  470. *minimum = min;  *maximum = max;
  471. return(max - min); /* returning the difference */
  472. }
  473.  
  474. /***************************************************************************
  475.  
  476.      write_levels()
  477.  
  478.      Returns:  void
  479.  
  480.      Purpose:  Write the level numbers for each term into the inverted file
  481.                depending on the total wdf of the term in the database and 
  482.                the user selected parameter NUMBER_OF_LEVELS.
  483.                The level numbers are marked 0, 1, 2, ... etc.  Level 0
  484.                refers to the highest frequency class, level 1 the next 
  485.                frequency class etc.  
  486.  
  487. **/
  488.  
  489. static void write_levels()
  490. {
  491. int    i,                   /* counter through the different levels       */ 
  492.        number;              /* holds NUMBER_OF_LEVELS                     */
  493. float  freq,                /* holds frequency of term in database        */
  494.        range,               /* holds diff. between highest & lowest freqs.*/
  495.        current_low,         /* tracks lower frequency of current level    */
  496.        current_high;        /* tracks higher frequency of current level   */
  497. float  high,                /* highest term frequency in database         */
  498.        low;                 /* lowest term frequency in database          */
  499. struct invert *inv_addr;    /* tracks current inverted file record        */
  500.  
  501. /* range holds the difference between highest & lowest totalwdf in dbse.  */
  502. range = get_freq_range(&low,&high);
  503. number = NUMBER_OF_LEVELS;  /* user specified global parameter            */
  504.  
  505. inv_addr = startinv;        /* start with the first term in inverted file */
  506. while(inv_addr) {           /* while a legitimate term was found          */
  507.   freq = total_wdf(inv_addr->term);
  508.   current_low = low;
  509.   for (i=(number-1);i>=0;i--) { 
  510.     if (i==0) current_high = high; else current_high = current_low + (range/number);
  511.     /* if the term's frequency is within this narrow range, then level = i*/
  512.     if ((freq >= current_low) && (freq <= current_high)) {
  513.        inv_addr->level = i;
  514.        break;
  515.     } 
  516.     current_low = current_high; /* loop through the frequency levels      */
  517.   }  /* ending for loop */
  518.   inv_addr = inv_addr->nextterm;  /* loop through other inv. file terms   */
  519. } 
  520.  
  521. }
  522.  
  523. /***************************************************************************
  524.  
  525.      generate_Rada_hierarchy()
  526.  
  527.      Returns:  void
  528.  
  529.      Purpose:  Create the levelptrs data structure and generate the hierarchy
  530.                according to Rada's algorithm
  531.  
  532. **/
  533.  
  534. static void generate_Rada_hierarchy()
  535. {
  536. struct termlist {
  537.   struct invert *term;       /* pointer to term in inverted file       */
  538.   int mark;                  /* equals 1 if term is propagated else 0  */
  539.   struct termlist *nextterm; /* pointer to next termlist record        */
  540. } termlistfile, *p, *q, *r; 
  541.  
  542. /* levelptrs is an array of pointers.  Each slot points to the start of 
  543.    the chain of termlist records for that level  */
  544.  
  545. struct termlist *levelptrs[NUMBER_OF_LEVELS];
  546.  
  547. int i;
  548. struct invert *inv_addr;    /* tracks current term in inverted file    */
  549. float coh, max_cohesion;
  550.  
  551. write_levels(); /* this routine computes and writes the level number for each */
  552.                 /* term in the inverted file                                  */
  553. for (i=0;i<NUMBER_OF_LEVELS;i++) levelptrs[i] = NULL; /* intializing the array*/
  554.  
  555. /* now create the termlist chain for each level  */
  556.  
  557. inv_addr = startinv;                /* start with first term in inverted file */
  558. while (inv_addr) {                  /* while there is a term there            */
  559.   p = (struct termlist *)malloc(sizeof(termlistfile)); /* get memory for termlist */
  560.   if (!p) {
  561.      (void) fprintf(output,"\nout of memory\n");
  562.      exit(1);
  563.   }
  564.   p->term = inv_addr;               /* assign the address of term in inverted file*/
  565.   p->mark = 0;                      /* initially term not linked */
  566.   /* Note: this term has been assigned to a frequency level already.  Now, if this */
  567.   /* is the first term read for this level then set the appropriate levelptrs entry*/
  568.   /* to point to this term    */
  569.   if (levelptrs[inv_addr->level] == NULL) {
  570.      levelptrs[inv_addr->level] = p;
  571.       p->nextterm = NULL;
  572.   }
  573.   else {  /* now this is not the first term encountered for this level, so simply  */
  574.           /* attach it to the front of the chain                                   */
  575.       p->nextterm = levelptrs[inv_addr->level];
  576.       levelptrs[inv_addr->level] = p;
  577.   }
  578.   inv_addr = inv_addr->nextterm;                /* process next inverted file term */
  579. } /* end while */
  580.  
  581.  
  582. /* start with each level and compute max-cohesion with previous level */
  583.  
  584. for (i=1;i<NUMBER_OF_LEVELS;i++) {
  585.    p = levelptrs[i];
  586.    while (p) {
  587.      max_cohesion = 0.0;
  588.      q = levelptrs[i-1];               /* q set to the previous level's first term */
  589.      while (q) {          /* as long as there are terms in this previous level ... */
  590.         coh = cohesion(p->term->term,q->term->term);
  591.         if (coh > max_cohesion) max_cohesion = coh;
  592.         q = q->nextterm;
  593.      }
  594.      /* max_cohesion for terms in p has been computed */
  595.      
  596.      /*  adding parent-child links and marking parents as propagated */
  597.  
  598.      q = levelptrs[i-1];
  599.      while (q && max_cohesion > 0.0) {
  600.         coh = cohesion(p->term->term,q->term->term);
  601.         if (coh == max_cohesion) {         /* this ensures multiple links possible */
  602.            add_link(q->term->term,p->term->term);  /* routine adds the actual link */
  603.            q->mark = 1;                /* to show that parent term has been linked */
  604.         } 
  605.         q = q->nextterm;
  606.      } /* end while(q) */
  607.      p = p->nextterm;                                /* go to next term in level i */
  608.      max_cohesion = 0.0;
  609.    }  /* end while(p) */
  610.  
  611. /* checking all terms in level[i-1] to make sure they have propagated */
  612.  
  613. q = levelptrs[i-1];
  614. while (q) {
  615.   if (q->mark == 0){                       /* i.e. term has no child in next level */
  616.      q->mark = 1; 
  617.      r = (struct termlist *)malloc(sizeof(termlistfile));
  618.      if (!r) { (void) fprintf(output,"\nout of memory\n");
  619.        exit(2);
  620.      }
  621.      r->term = q->term;  r->mark = 0; /* making a copy of term as its dummy child */
  622.      r->nextterm = levelptrs[i];  /* inserting r at beginning of level i chain */
  623.      levelptrs[i] = r;
  624.   }
  625. q = q->nextterm;
  626. }
  627. }  /* for */
  628. }
  629.   
  630. /***************************************************************************
  631.  
  632.      cohesion(term1,term2)
  633.  
  634.      Returns:  void
  635.    
  636.      Purpose:  Compute the cohesion between two terms 
  637.  
  638. **/
  639.  
  640. static float cohesion(term1,term2)
  641. char  term1[MAXWORD],    /* in: the two terms which are being            */
  642.       term2[MAXWORD];    /* in: compared to determine cohesion           */
  643. {
  644. float l1,                /* holds # of documents associated with term 1  */
  645.       l2,                /* holds # of documents associated with term 2  */
  646.       common;            /* holds # of documents in common               */
  647.  
  648. get_term_data(term1,term2,&l1,&l2,&common);
  649. return(common/(sqrt(l1 * l2)));
  650. }
  651.  
  652. /***************************************************************************
  653.  
  654.      get_term_data(term1,term2,l1,l2,common)
  655.  
  656.      Returns:  void
  657.  
  658.      Purpose:  Given two terms, it determines the number of documents in
  659.                each and in common between them.
  660.  
  661. **/
  662.  
  663. static void get_term_data(term1,term2,l1,l2,common)
  664. char  term1[MAXWORD],         /* in: term 1                                 */
  665.       term2[MAXWORD];         /* in: term 2                                 */
  666. float *l1,                    /* out: # of documents associated with term 1 */
  667.       *l2,                    /* out: # of documents associated with term 2 */
  668.       *common;                /* out: # of documents associated with both   */
  669. {
  670. struct invert *p, *q;         /* holds addresses of both terms in inv. file */
  671. struct doclist *doc_ad1, *doc_ad2; /* tracks addresses of doclists records  */
  672. int   count1,                 /* # of documents associated with term 1      */
  673.       count2,                 /* # of documents associated with term 2      */
  674.       com;                    /* # of documents in common                   */
  675.  
  676. p = find_term(term1);  q = find_term(term2);     /* find addresses of terms */
  677. doc_ad1 = p->doc;                     /* start with doclist record for term1*/
  678.  
  679. count1 = 0;  count2 = 0;  com = 0;    /* initialize */
  680.  
  681. /* first get length for document 1 and number of common terms */
  682.  
  683. while (doc_ad1) {
  684.   count1 = count1 +1;
  685.   doc_ad2 = q->doc;
  686.   /* for each doc. of term1 loop through all docs. of term2                 */
  687.   while (doc_ad2) {
  688.     if (doc_ad1->doc == doc_ad2->doc) {     /* if they are the same doc. #   */
  689.         com = com +1;
  690.         break;
  691.     }
  692.     doc_ad2 = doc_ad2->nextdoc;
  693.   }
  694.   doc_ad1 = doc_ad1->nextdoc;
  695. } 
  696.  
  697. /* now get length of document 2 */
  698.  
  699. doc_ad2 = q->doc;
  700. while (doc_ad2) {
  701.   count2 = count2 + 1;
  702.   doc_ad2 = doc_ad2->nextdoc;
  703. }
  704. *l1 = count1;  *l2 = count2;  *common = com;
  705. }
  706.  
  707. /***************************************************************************
  708.  
  709.      *find_term(term)
  710.  
  711.      Returns:  address of a struct invert record
  712.  
  713.      Purpose:  Search for a specified term in the inverted file and
  714.                return address of the corresponding inverted file record.
  715.  
  716. **/
  717.  
  718. static struct invert *find_term(term)
  719. char term[MAXWORD];         /* in: term to be located in inverted file   */
  720. {
  721. struct invert *inv_addr;    /* tracks addr. of current rec. in inv, file */
  722.  
  723. inv_addr = startinv;                        /* begin at top on inv. file */
  724. while(inv_addr) {
  725.   if (!strcmp(term,inv_addr->term)) return(inv_addr);
  726.   inv_addr = inv_addr->nextterm;
  727. }
  728. (void) fprintf(output,"Term %s not found\n",term);
  729. return(NULL);
  730. }
  731.  
  732. /***************************************************************************
  733.  
  734.      *get_mem_invert()
  735.  
  736.      Returns:  address of a struct invert record
  737.  
  738.      Purpose:  dynamically obtain enough memory to store 1 invert record.
  739.  
  740. **/
  741.  
  742.  
  743. static struct invert *get_mem_invert()
  744. {
  745. struct invert *record;
  746.  
  747. record = (struct invert *)malloc(sizeof(invfile));
  748. if (!record) {
  749.     (void) fprintf(output,"\nout of memory\n");
  750.     return(NULL);
  751. }
  752. return(record);
  753. }
  754.  
  755. /***************************************************************************
  756.  
  757.      *get_mem_doclist()
  758.  
  759.      Returns:  address of a struct doclist record
  760.  
  761.      Purpose:  dynamically obtain enough memory to store 1 doclist record.
  762.  
  763. **/
  764.  
  765. static struct doclist *get_mem_doclist()
  766. {
  767. struct doclist *record;
  768.  
  769. record = (struct doclist *)malloc(sizeof(doclistfile));
  770. if (!record) {
  771.     (void) fprintf(output,"\nout of memory\n");
  772.     return(NULL);
  773. }
  774. return(record);
  775. }
  776.  
  777. /***************************************************************************
  778.  
  779.      *get_mem_parentlist()
  780.  
  781.      Returns:  address of a struct parentlist record
  782.  
  783.      Purpose:  dynamically obtain enough memory to store i parentlist record
  784.  
  785. **/
  786.  
  787. static struct parentlist *get_mem_parentlist()
  788. {
  789. struct parentlist *record;
  790.  
  791. record = (struct parentlist *)malloc(sizeof(parentfile));
  792. if (!record) {
  793.     (void) fprintf(output,"\nout of memory\n");
  794.     return(NULL);
  795. }
  796. return(record);
  797. }
  798.  
  799. /***************************************************************************
  800.  
  801.  
  802.    *get_mem_childlist()
  803.  
  804.    Returns:  address of a struct childlist record
  805.  
  806.    Purpose:  dynamically obtain enough memory to store 1 childlist record
  807.  
  808. **/
  809.  
  810. static struct childlist *get_mem_childlist()
  811. {
  812. struct childlist *record;
  813.  
  814. record = (struct childlist *)malloc(sizeof(childfile));
  815. if (!record) {
  816.     (void) fprintf(output,"\nout of memory\n");
  817.     return(NULL);
  818. }
  819. return(record);
  820. }
  821.  
  822.  
  823.